# -*- coding:utf-8 -*-
# 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数

# 示例 1:
# 输入: [1,3,4,2,2]
# 输出: 2

# 示例 2:
# 输入: [3,1,3,4,2]
# 输出: 3

# 说明：
# 不能更改原数组（假设数组是只读的）
# 只能使用额外的 O(1) 的空间
# 时间复杂度小于 O(n2)
# 数组中只有一个重复的数字，但它可能不止重复出现一次

# # 题目理解错误 [1,4,4,2,4]可能出现这种不连续的数字
# class Solution(object):
#     def findDuplicate(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         max_n = 0;
#         total_sum = 0;
#         for n in nums:
#             if n > max_n:
#                 max_n = n;
#             total_sum += n;
#         repate_sum = total_sum - (1 + max_n) * max_n / 2;
#         repate_count = len(nums) - max_n;
#         return repate_sum / repate_count;

# # 想不通
# # 理由如下:
# # n+1个数字找出其中2个相同的，因为其中任何2个都有可能相等，所以理论上需要对任何2个都进行对比才能的出结果
# # 可是如此时间复杂度就不满足要求，因为至少是O(n2)

# # 因此题目中给与条件，一定影响了每2个都要对比一下的条件
# # 数组长度n+1 数值[1,n] 只有1个数值重复
# # 是怎么影响到了呢？
# class Solution(object):
#     def findDuplicate(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """

# 查看讨论区，获得解决思路
# 将数组看成链表，val是结点值也是下个节点的地址。因此这个问题就可以转换成判断链表有环，且找出入口节点---使用快慢指针
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow = 0;
        fast = 0;
        while True:
            slow = nums[slow];
            fast = nums[nums[fast]];
            if slow != fast:
                continue;
            head = 0;
            meet = fast;
            while nums[head] != nums[meet]:
                head = nums[head];
                meet = nums[meet];
            return nums[head];

t = Solution();
print t.findDuplicate([1,4,4,2,4]);

# # 知识点补充
# 1.给一个单链表，判断其中是否有环的存在
# 2.如果存在环，找出环的入口点
# 3.如果存在环，求出环上节点的个数
# 4.如果存在环，求出链表的长度
# 5.如果存在环，求出环上距离任意一个节点最远的点{对面节点}
# 6.（扩展）如何判断两个无环链表是否相交
# 7.（扩展）如果相交，求出第一个相交的节点

# 问题1： 单链是否有环
# 快慢指针
# fast slow 2个指针每一次 fast向前走2步 slow向前走一步
# 假设单链从head开始就是一个环，fast和slow都从head出发，每走一次fast都距离slow的背后近一步，并且fast会在slow的第一圈结尾处追上它
# 假设单链的环出现在中间的某一个地方，假设环的长度为R，那么当slow走到环的入口时，fast距离slow的背后一定<R，可以使用上面的思路证明slow没走完一圈就会被fast追上
# 结论：slow没有走完完整一圈的时候，fast就会追上slow

#{                   S                 }
#{        A         } {        X       }
#H-------------------E-----------------M
#                    |                 |
#                    |                 |
#                    |        R        |
#                    |                 |
#                    |                 |
#                    -------------------
# 问题2： 环的入口
# 假设 slow走的步数是S，那么fast的步数就是2S
# 假设 环的入口距离head的步数是A，fast和slow相遇的地点距离环的入口时X，则能推导出 A + X = S {1}
# 假设 环的长度是R，当fast和slow相遇时fast已经跑了N圈，则能推导出 S + NR = 2S {2}
# A + X = S
# S + NR = 2S
# 由上推倒出 A = NR - X
# 所以我们让一个指针从head出发，一个指针从距离环入口的X位置出发，它们一定会在环的入口相遇

# 问题3： 环上的节点数目
# 我们已经找到相遇的节点，从相遇节点向前走，一直走回相遇节点，即为环上节点的数目

# 问题4： 环的长度
# 从上已知环的入口，以及环的长度，可以很容易算出L = A + R

# 问题5： 环上距离最远的节点
# 求环上节点N最远的节点
# 快慢节点都从N节点开始向前走，快节点一次走2步，慢节点一次走一步
# 当快节点返回节点N时，慢节点所在的位置即是最远的节点

# 问题6： 如何判断两个无环链表是否相交
# 将其中一个链表首尾相连，问题转化为问题1，是否有环

# 问题7： 如果相交，求出第一个相交的节点
# 问题转化为问题2，求环的入口